/**
 * @Project : algorithm-learning
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/4/17 16:15
 */

#include <iostream>

using namespace std;

//class Solution {
//public:
//
//    // O(n) O(n)
//    string reverseWords(string s) {
//        string res = "";
//        for (int i = 0; i < s.size(); ++i) {
//            string tmp = "";
//            while (i < s.size() && s[i] != ' ') {
//                tmp += s[i++];
//            }
//            if (tmp != "") {
//                res = tmp + " " + res;
//            }
//        }
//        return res.substr(0, res.size() - 1);
//    }
//
//    // O(n) O(1)
//    string reverseWords(string s) {
//        for (int i = 0; i < s.size(); ++i) {
//            int j = i;
//            while (j < s.size() && s[j] != ' ') {
//                j++;
//            }
//            for (int l = i, r = j - 1; l < r; ++l, --r) {
//                swap(s[l], s[r]);
//            }
//            i = j;
//        }
//        for (int l = 0, r = s.size() - 1; l < r; ++l, --r) {
//            swap(s[l], s[r]);
//        }
//        int j = 0;
//        for (int i = 0; i < s.size(); ++i) {
//            if (s[i] != ' ') {
//                s[j++] = s[i];
//            } else {
//                if (j == 0) continue;
//                if (s[j - 1] != ' ') s[j++] = s[i];
//            }
//        }
//        return s[j - 1] == ' ' ? s.substr(0, j - 1) : s.substr(0, j);
//    }
//};

class Solution {
public:
    // O(n) O(1)
    string reverseWords(string s) {
        int idx = 0;
        int l = 0;
        int r = 0;

        for (; r < s.size(); ++r) {
            if (s[r] == ' ') {
                if (l < r) {
                    // 原地反转
                    for (int i = l, j = r - 1; i < j; ++i, --j) {
                        swap(s[i], s[j]);
                    }
                    // 去除空格
                    for (int i = idx, j = l; j < r; ++i, ++j) {
                        s[i] = s[j];
                    }
                    idx += r - l + 1;
                    s[idx - 1] = ' ';
                }
                l = r + 1;
            }
        }
        // 收尾
        if (l < r) {
            for (int i = l, j = r - 1; i < j; ++i, --j) {
                swap(s[i], s[j]);
            }
            for (int i = idx, j = l; j < r; ++i, ++j) {
                s[i] = s[j];
            }
            idx += r - l + 1;
            s[idx - 1] = ' ';
        }
        // 全部反转
        for (int i = 0, j = idx - 2; i < j; ++i, --j) {
            swap(s[i], s[j]);
        }
        // 去掉后面数据
        return s.substr(0, idx - 1);
    }
};

int main() {
    Solution sl;
    sl.reverseWords("the sky is blue");
    return 0;
}